package 每日一题OJ;

import java.util.Random;

/**
 * @author shy_black
 * @date 2019/8/19 23:32
 * @Description:
 *
 *
 * 1.快排中quickSort递归时必须判断 （l < r）,不然mid-1可能会数组越界(血的教训)
 * 2.快排中partition时判断与key值相等的条件(即while中嵌套的俩个while的条件)
 * -----首先他俩必须是右先，左后，其次每次进while时必须判断l<r,
 * -----在其次判断是否进while只需要其中一个判断当前与key相等---while (l < r && arr[key] >= arr[l])
 * -----如果两个while都判断，会乱
 * 3.判断当前一个元素与当前元素相等时，continue，这样可以做到去重（注意边界和特殊条件的判断）
 */
public class _128_最长连续序列 {
    public static void main(String[] args) {
        int num = 10000;//jvm默认栈容量可以承受数据大小
//        int num = 10;
        int[] arr = new int[num];
        long start = System.currentTimeMillis();
        Random random = new Random();
        for(int i = 0;i < num;i++) {
            arr[i] = random.nextInt(num);
        }
        int res = longestConsecutive(arr);
        for (int i = 0;i < num-1;i++) {
            if(arr[i] > arr[i+1]) {
                System.out.println("快排失败");
                return;
            }
//            System.out.print(i);
//            System.out.print("  ");
        }
        System.out.println("快排成功！！！");
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println("排序时长："+ time + "ms");
        System.out.println("\n" + res);
    }

    public static int longestConsecutive(int[] arr) {
        if (arr.length <= 1)
            return arr.length;

        quickSort(arr, 0, arr.length - 1);

        int num = arr[0];
        int tmp = 0;
        int len = 0;
        for (int i = 1; i < arr.length; i++) {
            if ((num + 1) == arr[i]) {
                tmp++;
                if (tmp > len)
                    len = tmp;
            } else if ((num) == arr[i]) {
                continue;
            } else {
                tmp = 0;
            }

            num = arr[i];
        }
        return len + 1;
    }


    private static void quickSort(int[] arr, int l, int r) {
        if (l < r) {//*********这个条件一定要加
            int mid = part(arr, l, r);
            quickSort(arr, l, mid - 1);
            quickSort(arr, mid + 1, r);
        }

    }

    private static int part(int[] arr, int l, int r) {
        Random random = new Random();
        int index = random.nextInt(r)%(r-l+1) + l;
        int key = arr[index];
        int left = l;
        int right = r;
//        key = arr[key];
        while (l < r) {
            //先看右边，依次往左递减
            while (key <= arr[r] && l < r) {
                r--;
            }
            //再看左边，依次往右递增
            while (key >= arr[l] && l < r) {
                l++;
            }
            //如果满足条件则交换
            if (l < r) {
                int t = arr[l];
                arr[l] = arr[r];
                arr[r] = t;
            }
        }
        //最后将基准 key 与 l和r 相等位置的数字交换
        arr[index] = arr[l];
        arr[l] = key;
        return l;


//        while (l < r) {
//            while (l < r && arr[key] < arr[r])
//                r--;
//            while (l < r && arr[key] >= arr[l])
//                l++;
//            if(l < r)
//                swap(arr, l, r);
//        }
//
//        swap(arr, l, key);
//        return l;
    }

    private static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}
